T1
Subtask 1 40 pts
直接暴力模拟即可。
Subtask 2 100 pts
不难发现重要的只有 A+B 和 C,而且可以发现 A+B+C 是一个定值。然后你发现答案其实就是 2k×C(modA+B+C),快速幂即可。
T2
Subtask 1 & 2 30 pts
直接暴力应该是可以的。
Subtask3 50 pts
可以每次建一个图,原点往扑克连一条流量为 1 的边,扑克往面值分别连一条流量为 1 的边,面值往汇点连一条容量为 1 的边。每次查询 [l,r] 的话直接只把 [l,r] 这段面值的点往汇点连边即可。
时间复杂度 懂得都懂。
Subtask4 10 pts
直接前缀和判断即可。
Subtask5 100 pts
将每个扑克的 u,v 相连,不难看出是一个树的时候一定不能满足全都选出来,如果里面有环则一定可以满足全都能选出来。
于是问题就是判定一个区间对应的点里是否包含树,直接离线下来扫描线即可。
时间复杂度 Θ(nlogn)。
T3
思路1:树状数组
我们考虑对于点v算出它的值那么就是:
t=1∑i−1(xt−dis[ut,v]×kt)
=t=1∑i−1(xt−(deep[v]−deep[ut])×kt)
=t=1∑i−1(xt+deep[ut]×kt)−deep[v]×t=1∑i−1kt
但是我们发现这个东西需要满足ut在1→v的路径上,怎么办呢?很简单,我们可以利用dfs的特性解决即可,然后这个东西直接用两个树状数组维护即可。
因为一个操作会加入删除各一次,所以总时间复杂度为Θ(mlogm+n)。
思路2:线段树
其实很套路,我们发现这个东西是给子树内加上一个等差数列(不是很严谨,大家意会一下),跟这道题有些相似。
于是就十分套路了。我们直接用线段树维护一个差分数组,每次操作就相当于给u节点加上x,给子树内其他节点加上−k。
查询操作就相当于询问1→u的路径和。
时间复杂度为Θ(mlog2n+n)。
T4
Subtask 1
这个怎么暴力都可以吧
Subtask 2
还是暴力,加上记忆化就可以了。
因为 m=2 好写很多。
Subtask 3 k=0
f0(n)=∏pi=n∑[∀i,j(i=j)gcd(pi,pj)=1]
令 τ(n) 为 n 的不同质因数的个数。
因为要求任意 pi,pj(i=j),gcd(pi,pj)=1 , 那么相同的质因数只会全部在其中一个 pi中。
每种不同的质因数有 m 种选法,那么 f0(n)=mτ(n)
可以看出,f0(n) 是一个积性函数。
具体实现可以欧拉筛出最小质因子,对询问的 n 分解质因数后将每一部分乘起来。
Subtask 4 k=0
fk(n)=∏pi=n∑∏fk−1(pi)
因为 f0(n) 是一个积性函数,可以猜测 fk(n) 也是一个积性函数。
考虑数学归纳法:
-
k=0 显然
-
k=0,假设 fk−1 为积性函数,对于任意互质两数 n,m 有:
fk(n)×fk(m)=∏pi=n∑∏fk−1(pi)×∏qi=m∑∏fk−1(qi)
=∏pi=n,∏qi=m∑∏fk−1(pi)×∏fk−1(qi)
=∏pi∏qi=nm∑∏fk−1(pi×qi)
=fk(nm)
现在只需要求出质数的幂的函数值即可。
fk(pw)=∑pi=w∑∏fk−1(ppi)
发现 fk(pw) 和 p 的值无关,所以可以提取出一个递推式:
fk,w=∑pi=w∑∏fr−1,pi
这个我也不知道怎么递推,不过给了分的...
tr 巨佬提出了一个 O(kmlog2n) 的做法 ?
Subtask 5
发现 f0={1,m,m....} , fk=(f0)mk
观察每一项,发现除了第一项系数都为 m。
可以钦定 m 的个数为 i ,那么对系数的贡献便为 mi
再考虑方案数,首先你得从 mk 个 f0 中选出 i 个来提供指数,然后用插板法算出分配指数的方案。
答案为:
fk,w=i=1∑wmi(imk)(i−1w−1)
这样单次询问可以暴力算组合数,是 O(∑w) 的,比 O(logn) 小。
瓶颈在于求 mk ,复杂度 O(qlogmod)
当然你用 ** 函数的知识会更好理解一些。